
希尔排序（Shell Sort）是插入排序的一种改进，又称缩小增量排序。它与插入排序的不同之处在于，它会优先比较距离较远的元素，而非相邻元素。

希尔排序的基本思想是，将待排序的元素序列划分为若干个子序列，分别进行直接插入排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序。

- 具体实现过程如下：
    - 首先确定一个增量 gap，通常初始值为序列长度的一半。
    - 将序列分组，对每一组执行插入排序，每个元素之间的距离为 gap。
    - 缩小增量，重复执行第2步，直到增量为1为止。
    - 最后执行一次插入排序，使得整个序列有序。

```js 
function shellSort(arr) {
  const len = arr.length;
  let gap = Math.floor(len / 2);
  while (gap > 0) {
    for (let i = gap; i < len; i++) {
      let j = i;
      while (j >= gap && arr[j - gap] > arr[j]) {
        [arr[j], arr[j - gap]] = [arr[j - gap], arr[j]];
        j -= gap;
      }
    }
    gap = Math.floor(gap / 2);
  }
  return arr;
}

```

:::info 
希尔排序的时间复杂度与增量序列的选择有关，最坏情况下为 O(n^2)，最好情况下为 O(n log n)。
:::